home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_12_04 / gage / compress.c < prev    next >
C/C++ Source or Header  |  1994-03-08  |  5KB  |  205 lines
  1. /* compress.c */
  2.  
  3. #include <stdio.h>
  4.  
  5. #define BLOCKSIZE 5000   /* Maximum block size */
  6. #define HASHSIZE  4096   /* Size of hash table */
  7. #define MAXCHARS   200   /* Char set per block */
  8. #define THRESHOLD    3   /* Minimum pair count */
  9.  
  10. unsigned char buffer[BLOCKSIZE]; /* Data block */
  11. unsigned char leftcode[256];     /* Pair table */
  12. unsigned char rightcode[256];    /* Pair table */
  13. unsigned char left[HASHSIZE];    /* Hash table */
  14. unsigned char right[HASHSIZE];   /* Hash table */
  15. unsigned char count[HASHSIZE];   /* Pair count */
  16. int size;        /* Size of current data block */
  17.  
  18. /* Function prototypes */
  19. int lookup (unsigned char, unsigned char);
  20. int fileread (FILE *);
  21. void filewrite (FILE *);
  22. void compress (FILE *, FILE *);
  23.  
  24. /* Return index of character pair in hash table */
  25. /* Deleted nodes have count of 1 for hashing */
  26. int lookup (unsigned char a, unsigned char b)
  27. {
  28.   int index;
  29.  
  30.   /* Compute hash key from both characters */
  31.   index = (a ^ (b << 5)) & (HASHSIZE-1);
  32.  
  33.   /* Search for pair or first empty slot */
  34.   while ((left[index] != a || right[index] != b) &&
  35.          count[index] != 0)
  36.     index = (index + 1) & (HASHSIZE-1);
  37.  
  38.   /* Store pair in table */
  39.   left[index] = a;
  40.   right[index] = b;
  41.   return index;
  42. }
  43.  
  44. /* Read next block from input file into buffer */
  45. int fileread (FILE *input)
  46. {
  47.   int c, index, used=0;
  48.  
  49.   /* Reset hash table and pair table */
  50.   for (c = 0; c < HASHSIZE; c++)
  51.     count[c] = 0;
  52.   for (c = 0; c < 256; c++) {
  53.     leftcode[c] = c;
  54.     rightcode[c] = 0;
  55.   }
  56.   size = 0;
  57.  
  58.   /* Read data until full or few unused chars */
  59.   while (size < BLOCKSIZE && used < MAXCHARS &&
  60.          (c = getc(input)) != EOF) {
  61.     if (size > 0) {
  62.       index = lookup(buffer[size-1],c);
  63.       if (count[index] < 255) ++count[index];
  64.     }
  65.     buffer[size++] = c;
  66.  
  67.     /* Use rightcode to flag data chars found */
  68.     if (!rightcode[c]) {
  69.       rightcode[c] = 1;
  70.       used++;
  71.     }
  72.   }
  73.   return c == EOF;
  74. }
  75.  
  76. /* Write each pair table and data block to output */
  77. void filewrite (FILE *output)
  78. {
  79.   int i, len, c = 0;
  80.  
  81.   /* For each character 0..255 */
  82.   while (c < 256) {
  83.  
  84.     /* If not a pair code, count run of literals */
  85.     if (c == leftcode[c]) {
  86.       len = 1; c++;
  87.       while (len<127 && c<256 && c==leftcode[c]) {
  88.         len++; c++;
  89.       }
  90.       putc(len + 127,output); len = 0;
  91.       if (c == 256) break;
  92.     }
  93.  
  94.     /* Else count run of pair codes */
  95.     else {
  96.       len = 0; c++;
  97.       while (len<127 && c<256 && c!=leftcode[c] || 
  98.           len<125 && c<254 && c+1!=leftcode[c+1]) {
  99.         len++; c++;
  100.       }
  101.       putc(len,output);
  102.       c -= len + 1;
  103.     }
  104.  
  105.     /* Write range of pairs to output */
  106.     for (i = 0; i <= len; i++) {
  107.       putc(leftcode[c],output);
  108.       if (c != leftcode[c])
  109.         putc(rightcode[c],output);
  110.       c++;
  111.     }
  112.   }
  113.  
  114.   /* Write size bytes and compressed data block */
  115.   putc(size/256,output);
  116.   putc(size%256,output);
  117.   fwrite(buffer,size,1,output);
  118. }
  119.  
  120. /* Compress from input file to output file */
  121. void compress (FILE *infile, FILE *outfile)
  122. {
  123.   int leftch, rightch, code, oldsize;
  124.   int index, r, w, best, done = 0;
  125.  
  126.   /* Compress each data block until end of file */
  127.   while (!done) {
  128.     done = fileread(infile);
  129.     code = 256;
  130.  
  131.     /* Compress this block */
  132.     for (;;) {
  133.  
  134.       /* Get next unused char for pair code */
  135.       for (code--; code >= 0; code--)
  136.         if (code==leftcode[code] && !rightcode[code])
  137.           break;
  138.  
  139.       /* Must quit if no unused chars left */
  140.       if (code < 0) break;
  141.  
  142.       /* Find most frequent pair of chars */
  143.       for (best=2, index=0; index<HASHSIZE; index++)
  144.         if (count[index] > best) {
  145.           best = count[index];
  146.           leftch = left[index];
  147.           rightch = right[index];
  148.         }
  149.  
  150.       /* Done if no more compression possible */
  151.       if (best < THRESHOLD) break;
  152.  
  153.       /* Replace pairs in data, adjust pair counts */
  154.       oldsize = size - 1;
  155.       for (w = 0, r = 0; r < oldsize; r++) {
  156.         if (buffer[r] == leftch &&
  157.             buffer[r+1] == rightch) {
  158.           if (r > 0) {
  159.             index = lookup(buffer[w-1],leftch);
  160.             if (count[index] > 1) --count[index];
  161.             index = lookup(buffer[w-1],code);
  162.             if (count[index] < 255) ++count[index];
  163.           }
  164.           if (r < oldsize - 1) {
  165.             index = lookup(rightch,buffer[r+2]);
  166.             if (count[index] > 1) --count[index];
  167.             index = lookup(code,buffer[r+2]);
  168.             if (count[index] < 255) ++count[index];
  169.           }
  170.           buffer[w++] = code;
  171.           r++; size--;
  172.         }
  173.         else buffer[w++] = buffer[r];
  174.       }
  175.       buffer[w] = buffer[r];
  176.  
  177.       /* Add to pair substitution table */
  178.       leftcode[code] = leftch;
  179.       rightcode[code] = rightch;
  180.  
  181.       /* Delete pair from hash table */
  182.      index = lookup(leftch,rightch);
  183.      count[index] = 1;
  184.     }
  185.     filewrite(outfile);
  186.   }
  187. }
  188.  
  189. void main (int argc, char *argv[])
  190. {
  191.   FILE *infile, *outfile;
  192.  
  193.   if (argc != 3)
  194.     printf("Usage: compress infile outfile\n");
  195.   else if ((infile=fopen(argv[1],"rb"))==NULL)
  196.     printf("Error opening input %s\n",argv[1]);
  197.   else if ((outfile=fopen(argv[2],"wb"))==NULL)
  198.     printf("Error opening output %s\n",argv[2]);
  199.   else {
  200.     compress(infile,outfile);
  201.     fclose(outfile);
  202.     fclose(infile);
  203.   }
  204. }
  205.